package com.lsa.iview.trees;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;

import com.lsa.helpers.tree.ITree;
import com.lsa.helpers.tree.ITreeNode;

public class BinaryTree<E> implements ITree<E>, Iterable<E> {
	private Node<E> root;
	private final Comparator<E> comparator;
	
	public BinaryTree(Comparator<E> comparator) {
		this.comparator = comparator;
	}
	
	public Comparator<E> getComparator() {
		return comparator;
	}

	public Node<E> insert(E e) {
		return insert(new Node<E>(e));
	}

	public Node<E> insert(Node<E> n) {
		if (n == null) {
			return null;
		}
		if (root == null) {
			root = n;
		}
		else {
			Node<E> tmp = root;
			Node<E> prev = null;
			boolean isLeft;
			
			do
			{
				isLeft = comparator.compare(tmp.data, n.data) >= 0;
				prev = tmp;
				if (isLeft) {
					tmp = tmp.left;
				}
				else {
					tmp = tmp.right;
				}
				
			}
			while(tmp != null);
			
			if (isLeft) {
				prev.setLeft(n);
			}
			else {
				prev.setRight(n);
			}
		}
		return n;
	}
	
	public boolean contains(E e) {
		return lookupNode(e) != null;
	}
	
	public Node<E> lookupNode(E e) {
		Node<E> result = null;
		
		Node<E> tmp = root;
		while(tmp != null) {
			if (comparator.compare(tmp.data, e) > 0) {
				tmp = tmp.left;
			}
			else if (comparator.compare(tmp.data, e) < 0) {
				tmp = tmp.right;
			}
			else {
				result = tmp;
				break;
			}
		}
		return result;
	}
	
	@Override
	public Node<E> getRoot() {
		return root;
	}

	public static class Node<E> implements ITreeNode<E>{
		private Node<E> left;
		private Node<E> right;
		private Node<E> parent;
		private E data;
		
		public Node(E data) {
			super();
			this.data = data;
		}

		public E getData() {
			return data;
		}
		
		public void setData(E data) {
			this.data = data;
		}
		
		public Node<E> getLeft() {
			return left;
		}

		public Node<E> getRight() {
			return right;
		}
		
		public void setLeft(Node<E> n) {
			this.left = n;
			if (n != null) {
				n.setParent(this);
			}
		}

		public void setRight(Node<E> n) {
			this.right = n;
			if (n != null) {
				n.setParent(this);
			}
		}
		
		public Node<E> getParent() {
			return parent;
		}

		public void setParent(Node<E> parent) {
			this.parent = parent;
		}

		@Override
		public List<ITreeNode<E>> getChildren() {
			if (left == null && right == null) {
				return Collections.emptyList();
			}
			else if (left == null) {
				return Arrays.asList((ITreeNode<E>)right);
			}
			else if (right == null) {
				return Arrays.asList((ITreeNode<E>)left);
			}
			return Arrays.asList((ITreeNode<E>)left, (ITreeNode<E>)right);
		}

		@Override
		public String toString() {
			return String.format("[L=%s, R=%s, e=%s]", left, right, data);
//			return String.format("[L=%s, R=%s, e=%s]", (left != null? left.data : "<null>"), (right != null? right.data : "<null>"), data); // non-recursive version
		}
	}

	@Override
	public int size() {
		return size(root);
	}
	
	private int size(Node<E> n) {
		if (n == null) {
			return 0;
		}
		return 1+size(n.left) + size(n.right);
	}

	@Override
	public String toString() {
		return String.format("BinaryTree [root=%s]", root);
	}

	@Override
	public Iterator<E> iterator() {
		return BinaryTreeUtils.iterator(BinaryTreeUtils.min(root));
	}
}
